package com.example.daiyinuo.leetcode;

/**
 * 给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算 你所能获取的最大利润。你最多可以完成两笔交易
 * <p>
 * 输入：p ri ce s = [ 3 , 3 , 5 , 0 , 0 , 3 , 1 , 4 ] 输出：6
 * 解 释 ： 在 第 4 天 （ 股 票 价 格 = 0 ） 的 时 候 买 入 ，
 * 在 第 6 天（ 股 票 价 格 = 3 ） 的 时 候 卖 出，这笔交易所能获得利润 = 3 -0 = 3 。
 * 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候 卖出，
 * 这笔交易所能获得利润 = 4 -1 = 3
 * <p>
 * 我们定义dp[i][j]表示 在j天结束之后最多交易i次所能获得的最大利润。
 * 很明显i只能是0，1，2。表示要么没有交易，要么交易一次，要么交易两次，但不能超过两次，
 * dp的定义如下 int[][] dp = new int[3][prices .length];
 * 如果不进行任何交易 则 dp[i][j] = dp[i][j-1] 则最大的就是前一天的最大收益
 *  * 如果选择卖出股票，dp[i][j] = prices[j] - prices[k] + dp[i-1][k-1], k=[0..j-1]
 * prices[j] - prices[k]表示的是在第k天买入一支股票，然后再第j天把它给卖掉所获得的利润，
 * 其中k的范围是0…j -1。买一次卖一次算一次完整的交易，dp[i-1][k-1]表示的是在前k-1天最多进行i-1次交易所获得的的最大利润。
 */
public class leetCode123 {

    public static int getBestPrice(int prices[]) {
        int length = prices.length;
        int[][] dp = new int[3][length];
        for (int i = 1; i < 3; i++) {
            for (int j = 1; j < length; j++) {
                for (int k = j - 1; k >= 0; k--) {
                    int max = 0;
                    if (k == 0) {
                        //k等于0 表示第一天买入
                        max = Math.max(dp[i][j - 1], prices[j] - prices[k]);
                    } else {
                        //递推公式
//要么第j天不进行任何操作，要么第j天卖出一支股票。如果卖出股票我们需要找到卖出
//股票的最大利润（注意这里k不一定是买入股票最低价的那天，这里的最大利润还需要
//包含前面交易的利润，所以是prices[j] - prices[k] + dp[i - 1][k - 1]）
                        max = Math.max(dp[i][j - 1], prices[j] - prices[k] + dp[i - 1][k - 1]);
                    }
                    System.out.println("i=" + i + ",j=" + j + ",k=" + k + ",max=" + max);
                    dp[i][j] = Math.max(dp[i][j], max);
                }
            }
        }


        return dp[2][prices.length - 1];
    }

    public static void main(String[] args) {
        int[] prices = new int[]{3, 3, 5, 0, 0, 3, 1, 4};
        System.out.println(maxProfit(prices));
    }

    public static int maxProfit(int[] prices) {
        int[][] dp = new int[3][prices.length];
//i是交易的次数，从1开始，如果是0表示没有交易，这个不需要计算
        for (int i = 1; i <= 2; i++) {
            int max = Integer.MIN_VALUE / 2;
            for (int j = 1; j < prices.length; j++) {
//记录前j-1天买一支股票的最大利润
                max = Math.max(max, dp[i - 1][j - 1] - prices[j - 1]);
//dp[i][j - 1] 表示第j天没有任何操作的最大利润，
// prices[j] + max 表示第j天卖出一支股票的最大利润
                dp[i][j] = Math.max(dp[i][j - 1], prices[j] + max);
            }
        }
        return dp[2][prices.length - 1];
    }


    public static int maxValue(int [] prices){
        int [][]dp = new int[3][prices.length];

        for(int i=1;i<3;i++){
            int max = 0;
            for(int j=1;j<prices.length;j++){
                //记录j-1那天 买入 股票的最大利润
                max = Math.max(max,dp[i-1][j-1]-prices[j-1]);

                dp[i][j] = Math.max(dp[i][j-1],prices[j]+max);
            }
        }


        return dp[2][prices.length-1];
    }
}
